package bst.bst_map;

public class BSTreeMap {
    private TreeNode root;
    private int size;

    public BSTreeMap(){
        this.root = null;
        this.size = 0;
    }

    public String put(Long key,String value){
        //1. 插入  当搜索树中没有这个 key 的时候，就是插入这个键值对，返回 null
        //2. 更新  当搜索树中有这个 key 的时候，就是将这个 key 进行更像，返回原来的 value
        if(root == null){
            root = new TreeNode(key,value);
            this.size = 1;
            return  null;
        }

        TreeNode parent = null;
        TreeNode cur = root;
        int c = -1;
        while(cur != null){
            c = key.compareTo(cur.key);
            if(c == 0){
                String oldValue = cur.value;
                cur.value = value;
                return oldValue;
            }else if(c < 0){
                parent = cur;
                cur = cur.left;
            }else{
                parent = cur;
                cur = cur.right;
            }
        }

        TreeNode node = new TreeNode(key,value);
        if(c < 0){
            parent.left = node;
        }else{
            parent.right = node;
        }
        size++;

        return null;
    }

    public String get(Long key){
        TreeNode cur = root;
        while(cur != null){
            int c = key.compareTo(cur.key);
            if(c == 0){
                return cur.value;
            }else if(c < 0){
                cur = cur.left;
            }else{
                cur = cur.right;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        BSTreeMap map = new BSTreeMap();
        map.put(1L,"一");
        map.put(2L,"二");
        map.put(30L,"三十");

        System.out.println(map.get(1L));    //一
        System.out.println(map.get(30L));   //三十
        System.out.println(map.get(3L));    //null
    }
}
